//  给定一棵二叉树的根节点root
//  要求将这棵二叉树转换为一个已排序的双向循环链表，要求不能创建新的节点，只能调整树中节点指针的指向
// 思路，中序递归遍历
// 通过中序递归遍历可以将二叉树升序排列输出，这道题需要在中序遍历的同时，将节点的左右指向进行改变，使用head，tail存放双向链表的头尾节点，然后从根节点开始，进行
// 中序递归遍历

function treeToDoubleList(root) {
    if (!root) {
        return null
    }
    function dfs(root) {
        if (!root) {
            return null
        }
        dfs(root.left)
        if (!head) {
            head = root
        } else {
            // right指向下一位，left指向上一位
            tail.right = root
            root.left = tail
        }
        // 不断更新tail，知道最后一个节点，tail可以标记为上一次节点，root为当前节点
        tail = root
        dfs(root.right)
    }
    let head = null
    let tail = null
    dfs(root)
    head.left = tail
    tail.right = head
    return head
}
const root = {
    val: 4,
    left: {
        val: 3,
        left: {
            val: 2,
        },
        right: {
            val: 3.5,
        },
    },
    right: {
        val: 6,
    },
};

console.log(treeToDoubleList(root))